Technological breakthroughs allow us to collect data with increasing spatiotemporal resolution from complex interaction systems.

In graphical models, factor graphs, and more generally energy-based models, the interactions between variables are encoded by a graph, a hypergraph, or, in the most general case, a partially ordered set (poset). Inference on such probabilistic models cannot be performed exactly due to cycles in the underlying structures of interaction. Instead, one resorts to approximate variational inference by optimizing the Bethe free energy. Critical points of the Bethe free energy correspond to fixed points of the associated Belief Propagation algorithm. A full characterization of these critical points for general graphs, hypergraphs, and posets with a finite number of variables is still an open problem. We show that, for hypergraphs and posets with chains of length at most 1, changing the poset of interactions of the probabilistic model to one with the same homotopy type induces a bijection between the critical points of the associated free energy. This result extends and unifies classical results that assume specific forms of collapsibility to prove uniqueness of the critical points of the Bethe free energy.

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. The paper introduces a series of bounds on some approximations of the partition function for graphical models. They first bound from below the lower bound provided by'ExactOnTree' approximations, and then show that, for a binary pariwise models, clamping (i.e. The paper is clear and interesting. Insight about the quality of lower bounds that are used in many applications is obiously usefull.

Neural Information Processing Systems http://nips.cc/

Belief propagation is a fundamental message-passing algorithm for probabilistic reasoning and inference in graphical models. While it is known to be exact on trees, in most applications belief propagation is run on graphs with cycles. Understanding the behavior of "loopy" belief propagation has been a major challenge for researchers in machine learning and other fields, and positive convergence results for BP are known under strong assumptions which imply the underlying graphical model exhibits decay of correlations. We show, building on previous work of Dembo and Montanari, that under a natural initialization BP converges quickly to the global optimum of the Bethe free energy for Ising models on arbitrary graphs, as long as the Ising model is ferromagnetic (i.e.

It was recently proved using graph covers (Ruozzi, 2012) that the Bethe partition function is upper bounded by the true partition function for a binary pairwise model that is attractive. Here we provide a new, arguably simpler proof from first principles. We make use of the idea of clamping a variable to a particular value. For an attractive model, we show that summing over the Bethe partition functions for each sub-model obtained after clamping any variable can only raise (and hence improve) the approximation. In fact, we derive a stronger result that may have other useful implications. Repeatedly clamping until we obtain a model with no cycles, where the Bethe approximation is exact, yields the result. We also provide a related lower bound on a broad class of approximate partition functions of general pairwise multi-label models that depends only on the topology. We demonstrate that clamping a few wisely chosen variables can be of practical value by dramatically reducing approximation error.

This paper considers the variational approach to the inference problem on certain type of temporal graphical models. It defines a convex formulation of the Bethe free energy, resulting in a method with optimal convergence guarantees. The authors derive Expectation-Propagation fixed point equations and gradient-based updates for solving the optimization problem. A toy example is used to illustrate the approach in the context of transportation dynamics and it is shown that the proposed method outperforms sampling, extended Kalman Filtering and a neural network method. In the variational formulation, the optimization problem is generally non-convex, due to the entropy terms.

Technological breakthroughs allow us to collect data with increasing spatiotemporal resolution from complex interaction systems. The combination of highresolution observations, expressive dynamic models, and efficient machine learning algorithms can lead to crucial insights into complex interaction dynamics and the functions of these systems. In this paper, we formulate the dynamics of a complex interacting network as a stochastic process driven by a sequence of events, and develop expectation propagation algorithms to make inferences from noisy observations. To avoid getting stuck at a local optimum, we formulate the problem of minimizing Bethe free energy as a constrained primal problem and take advantage of the concavity of dual problem in the feasible domain of dual variables guaranteed by duality theorem. Our expectation propagation algorithms demonstrate better performance in inferring the interaction dynamics in complex transportation networks than competing models such as particle filter, extended Kalman filter, and deep neural networks.